////给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。 
////
//// 
////
//// 示例 1： 
////
//// 
////输入: root = [5,3,6,2,4,null,7], k = 9
////输出: true
//// 
////
//// 示例 2： 
////
//// 
////输入: root = [5,3,6,2,4,null,7], k = 28
////输出: false
//// 
////
//// 
////
//// 提示: 
////
//// 
//// 二叉树的节点个数的范围是 [1, 10⁴]. 
//// -10⁴ <= Node.val <= 10⁴ 
//// root 为二叉搜索树 
//// -10⁵ <= k <= 10⁵ 
//// 
//// 👍 374 👎 0
//


package leetcode.editor.cn;

//两数之和 IV - 输入 BST

import Entity.TreeNode;

import java.util.HashSet;
import java.util.Set;

public class P653_两数之和IV输入BST {
    public static void main(String[] args) {
        Solution solution = new P653_两数之和IV输入BST().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        Set<Integer> set = new HashSet<>();

        /**
         * 使用深度遍历 
         * 每次遍历保存节点值，并遍历的同时检查值的另一个值是否存在保存的表里面
         */
        public boolean findTarget(TreeNode root, int k) {
            if (root == null) {
                return false;
            }
            if (set.contains(k - root.val)) {
                return true;
            }
            set.add(root.val);
            return findTarget(root.left, k) || findTarget(root.right, k);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}